home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / os2 / pccts.zip / SET.C < prev    next >
C/C++ Source or Header  |  1992-12-08  |  14KB  |  676 lines
  1. /*    set.c
  2.  
  3.     The following is a general-purpose set library originally developed
  4.     by Hank Dietz and enhanced by Terence Parr to allow dynamic sets.
  5.     
  6.     Sets are now structs containing the #words in the set and
  7.     a pointer to the actual set words.
  8.     
  9.     Generally, sets need not be explicitly allocated.  They are
  10.     created/extended/shrunk when appropriate (e.g. in set_of()).
  11.     HOWEVER, sets need to be destroyed (free()ed) when they go out of scope
  12.     or are otherwise no longer needed.  A routine is provided to
  13.     free a set.
  14.     
  15.     Sets can be explicitly created with set_new(s, max_elem).
  16.     
  17.     Sets can be declared to have minimum size to reduce realloc traffic.
  18.     Default minimum size = 1.
  19.     
  20.     Sets can be explicitly initialized to have no elements (set.n == 0)
  21.     by using the 'empty' initializer:
  22.     
  23.     Examples:
  24.         set a = empty;    -- set_deg(a) == 0
  25.         
  26.         return( empty );
  27.     
  28.     Example set creation and destruction:
  29.     
  30.     set
  31.     set_of2(e,g)
  32.     unsigned e,g;
  33.     {
  34.         set a,b,c;
  35.         
  36.         b = set_of(e);        -- Creates space for b and sticks in e
  37.         set_new(c, g);        -- set_new(); set_orel() ==> set_of()
  38.         set_orel(g, &c);
  39.         a = set_or(b, c);
  40.         .
  41.         .
  42.         .
  43.         set_free(b);
  44.         set_free(c);
  45.         return( a );
  46.     }
  47.  
  48.     1987 by Hank Dietz
  49.     
  50.     Modified by:
  51.         Terence Parr
  52.         Purdue University
  53.         October 1989
  54. */
  55.  
  56. #include <stdio.h>
  57. #ifdef MEMCHK
  58. #include "trax.h"
  59. #else
  60. char *calloc(), *malloc(), *realloc();
  61. #endif
  62. #include "set.h"
  63.  
  64. /* elems can be a maximum of 32 bits */
  65. static unsigned bitmask[] = {
  66.     0x00000001, 0x00000002, 0x00000004, 0x00000008,
  67.     0x00000010, 0x00000020, 0x00000040, 0x00000080,
  68.     0x00000100, 0x00000200, 0x00000400, 0x00000800,
  69.     0x00001000, 0x00002000, 0x00004000, 0x00008000,
  70.     0x00010000, 0x00020000, 0x00040000, 0x00080000,
  71.     0x00100000, 0x00200000, 0x00400000, 0x00800000,
  72.     0x01000000, 0x02000000, 0x04000000, 0x08000000,
  73.     0x10000000, 0x20000000, 0x40000000, 0x80000000
  74. };
  75.  
  76. set empty = set_init;
  77. static unsigned min=1;
  78.  
  79. #define StrSize        200
  80.  
  81. #ifdef MEMCHK
  82. #define CHK(a)                    \
  83.     if ( a.setword != NULL )    \
  84.       if ( !valid(a.setword) )    \
  85.         {fprintf(stderr, "%s(%d): invalid set\n",__FILE__,__LINE__); exit(-1);}
  86. #else
  87. #define CHK(a)
  88. #endif
  89.  
  90. /*
  91.  * Set the minimum size (in words) of a set to reduce realloc calls
  92.  */
  93. void
  94. set_size(n)
  95. unsigned n;
  96. {
  97.     min = n;
  98. }
  99.  
  100. unsigned int
  101. set_deg(a)
  102. set a;
  103. {
  104.     /* Fast compute degree of a set... the number
  105.        of elements present in the set.  Assumes
  106.        that all word bits are used in the set
  107.        and that SETSIZE(a) is a multiple of WORDSIZE.
  108.     */
  109.     register unsigned *p = &(a.setword[0]);
  110.     register unsigned *endp = &(a.setword[a.n]);
  111.     register unsigned degree = 0;
  112.  
  113.     CHK(a);
  114.     if ( a.n == 0 ) return(0);
  115.     while ( p < endp )
  116.     {
  117.         register unsigned t = *p;
  118.         register unsigned *b = &(bitmask[0]);
  119.         do {
  120.             if (t & *b) ++degree;
  121.         } while (++b < &(bitmask[WORDSIZE]));
  122.         p++;
  123.     }
  124.  
  125.     return(degree);
  126. }
  127.  
  128. set
  129. set_or(b,c)
  130. set b, c;
  131. {
  132.     /* Fast set union operation */
  133.     /* resultant set size is max(b, c); */
  134.     set *big;
  135.     set t;
  136.     unsigned int m,n;
  137.     register unsigned *r, *p, *q, *endp;
  138.  
  139.     CHK(b); CHK(c);
  140.     t = empty;
  141.     if (b.n > c.n) {big= &b; m=b.n; n=c.n;} else {big= &c; m=c.n; n=b.n;}
  142.     set_ext(&t, m);
  143.     r = t.setword;
  144.  
  145.     /* Or b,c until max of smaller set */
  146.     q = c.setword;
  147.     p = b.setword;
  148.     endp = &(b.setword[n]);
  149.     while ( p < endp ) *r++ = *p++ | *q++;    
  150.  
  151.     /* Copy rest of bigger set into result */
  152.     p = &(big->setword[n]);
  153.     endp = &(big->setword[m]);
  154.     while ( p < endp ) *r++ = *p++;
  155.  
  156.     return(t);
  157. }
  158.  
  159. set
  160. set_and(b,c)
  161. set b, c;
  162. {
  163.     /* Fast set intersection operation */
  164.     /* resultant set size is min(b, c); */
  165.     set t;
  166.     unsigned int n;
  167.     register unsigned *r, *p, *q, *endp;
  168.  
  169.     CHK(b); CHK(c);
  170.     t = empty;
  171.     n = (b.n > c.n) ? c.n : b.n;
  172.     if ( n == 0 ) return t;        /* TJP 4-27-92 fixed for empty set */
  173.     set_ext(&t, n);
  174.     r = t.setword;
  175.  
  176.     /* & b,c until max of smaller set */
  177.     q = c.setword;
  178.     p = b.setword;
  179.     endp = &(b.setword[n]);
  180.     while ( p < endp ) *r++ = *p++ & *q++;    
  181.  
  182.     return(t);
  183. }
  184.  
  185. set
  186. set_dif(b,c)
  187. set b, c;
  188. {
  189.     /* Fast set difference operation b - c */
  190.     /* resultant set size is size(b) */
  191.     set t;
  192.     unsigned int n;
  193.     register unsigned *r, *p, *q, *endp;
  194.  
  195.     CHK(b); CHK(c);
  196.     t = empty;
  197.     n = (b.n <= c.n) ? b.n : c.n ;
  198.     if ( b.n == 0 ) return t;        /* TJP 4-27-92 fixed for empty set */
  199.                                     /* WEC 12-1-92 fixed for c.n = 0 */
  200.     set_ext(&t, b.n);
  201.     r = t.setword;
  202.  
  203.     /* Dif b,c until smaller set size */
  204.     q = c.setword;
  205.     p = b.setword;
  206.     endp = &(b.setword[n]);
  207.     while ( p < endp ) *r++ = *p++ & (~ *q++);    
  208.  
  209.     /* Copy rest of b into result if size(b) > c */
  210.     if ( b.n > n )
  211.     {
  212.         p = &(b.setword[n]);
  213.         endp = &(b.setword[b.n]);
  214.         while ( p < endp ) *r++ = *p++;
  215.     }
  216.  
  217.     return(t);
  218. }
  219.  
  220. set
  221. set_of(b)
  222. unsigned b;
  223. {
  224.     /* Fast singleton set constructor operation */
  225.     static set a;
  226.  
  227.     if ( b == nil ) return( empty );
  228.     set_new(a, b);
  229.     a.setword[DIVWORD(b)] = bitmask[MODWORD(b)];
  230.  
  231.     return(a);
  232. }
  233.  
  234. /*
  235.  * Extend (or shrink) the set passed in to have n words.
  236.  *
  237.  * if n is smaller than the minimum, boost n to have the minimum.
  238.  * if the new set size is the same as the old one, do nothing.
  239.  *
  240.  * TJP 4-27-92 Fixed so won't try to alloc 0 bytes
  241.  */
  242. void
  243. set_ext(a, n)
  244. set *a;
  245. unsigned int n;
  246. {
  247.     register unsigned *p;
  248.     register unsigned *endp;
  249.     unsigned int size;
  250.     
  251.     CHK((*a));
  252.     if ( a->n == 0 )
  253.     {
  254.         if ( n == 0 ) return;
  255.         a->setword = (unsigned *) calloc(n, BytesPerWord);
  256.         if ( a->setword == NULL )
  257.         {
  258.             fprintf(stderr, "set_ext(%d words): cannot allocate set\n", n);
  259.             *((char *)5) = 1;
  260.             exit(-1);
  261.         }
  262.         a->n = n;
  263.         return;
  264.     }
  265.     if ( n < min ) n = min;
  266.     if ( a->n == n || n == 0 ) return;
  267.     size = a->n;
  268.     a->n = n;
  269.     a->setword = (unsigned *) realloc( a->setword, (n*BytesPerWord) );
  270.     if ( a->setword == NULL )
  271.     {
  272.         fprintf(stderr, "set_ext(%d words): cannot allocate set\n", n);
  273.         exit(-1);
  274.     }
  275.  
  276.     p    = &(a->setword[size]);        /* clear from old size to new size */
  277.     endp = &(a->setword[a->n]);
  278.     do {
  279.         *p++ = 0;
  280.     } while ( p < endp );
  281. }
  282.  
  283. set
  284. set_not(a)
  285. set a;
  286. {
  287.     /* Fast not of set a (assumes all bits used) */
  288.     /* size of resultant set is size(a) */
  289.     /* ~empty = empty cause we don't know how bit to make set */
  290.     set t;
  291.     register unsigned *r;
  292.     register unsigned *p = a.setword;
  293.     register unsigned *endp = &(a.setword[a.n]);
  294.  
  295.     CHK(a);
  296.     t = empty;
  297.     if ( a.n == 0 ) return( empty );
  298.     set_ext(&t, a.n);
  299.     r = t.setword;
  300.     
  301.     do {
  302.         *r++ = (~ *p++);
  303.     } while ( p < endp );
  304.  
  305.     return(t);
  306. }
  307.  
  308. int
  309. set_equ(a,b)
  310. set a, b;
  311. {
  312.     /* Fast set equality comparison operation */
  313.     register unsigned *p = a.setword;
  314.     register unsigned *q = b.setword;
  315.     register unsigned *endp = &(a.setword[a.n]);
  316.  
  317.     CHK(a); CHK(b);
  318.     if ( a.n != b.n ) return(0);
  319.     else if ( a.n==0 ) return(1);    /* empty == empty */
  320.     
  321.     do {
  322.         if (*p != *q) return(0);
  323.         ++q;
  324.     } while ( ++p < endp );
  325.  
  326.     return(1);
  327. }
  328.  
  329. int
  330. set_sub(a,b)
  331. set a, b;
  332. {
  333.     /* Fast check for a is a proper subset of b (alias a < b) */
  334.     register unsigned *p = a.setword;
  335.     register unsigned *q = b.setword;
  336.     register unsigned *endp = &(a.setword[a.n]);
  337.     register int asubset = 0;
  338.  
  339.     CHK(a); CHK(b);
  340.     if ( a.n > b.n ) return(0);
  341.     if ( a.n == 0 ) return(1);        /* empty is sub of everything */
  342.     if (a.n==0 && b.n==0) return(1);/* empty prop sub of empty */
  343.  
  344.     do {
  345.         /* Prune tests based on guess that most set words
  346.            will match, particularly if a is a subset of b.
  347.         */
  348.         if (*p != *q) {
  349.             if (*p & ~(*q)) {
  350.                 /* Fail -- a contains something b does not */
  351.                 return(0);
  352.             }
  353.             /* At least this word was a proper subset, hence
  354.                even if all other words are equal, a is a
  355.                proper subset of b.
  356.             */
  357.             asubset = 1;
  358.         }
  359.         ++q;
  360.     } while (++p < endp);
  361.  
  362.     /* at this point, a,b are equ or a subset */
  363.     if ( asubset || b.n == a.n ) return(asubset);
  364.     
  365.     /* if !asubset, size(b) > size(a), then a=b and must check rest of b */
  366.     p = q;
  367.     endp = &(a.setword[b.n]);
  368.     do
  369.     {
  370.         if ( *p++ ) return(1);
  371.     } while ( p < endp );
  372.  
  373.     return(0);
  374. }
  375.  
  376. unsigned
  377. set_int(b)
  378. set b;
  379. {
  380.     /* Fast pick any element of the set b */
  381.     register unsigned *p = b.setword;
  382.     register unsigned *endp = &(b.setword[b.n]);
  383.  
  384.     CHK(b);
  385.     if ( b.n == 0 ) return( nil );
  386.  
  387.     do {
  388.         if (*p) {
  389.             /* Found a non-empty word of the set */
  390.             register unsigned i = ((p - b.setword) << LogWordSize);
  391.             register unsigned t = *p;
  392.             p = &(bitmask[0]);
  393.             while (!(*p & t)) {
  394.                 ++i; ++p;
  395.             }
  396.             return(i);
  397.         }
  398.     } while (++p < endp);
  399.  
  400.     /* Empty -- only element it contains is nil */
  401.     return(nil);
  402. }
  403.  
  404. int
  405. set_el(b,a)
  406. unsigned b;
  407. set a;
  408. {
  409.     CHK(a);
  410.     /* nil is an element of every set */
  411.     if (b == nil) return(1);
  412.     if ( a.n == 0 || NumWords(b) > a.n ) return(0);
  413.     
  414.     /* Otherwise, we have to check */
  415.     return( a.setword[DIVWORD(b)] & bitmask[MODWORD(b)] );
  416. }
  417.  
  418. set_nil(a)
  419. set a;
  420. {
  421.     /* Fast check for nil set */
  422.     register unsigned *p = a.setword;
  423.     register unsigned *endp = &(a.setword[a.n]);
  424.  
  425.     CHK(a);
  426.     if ( a.n == 0 ) return(1);
  427.     /* The set is not empty if any word used to store
  428.        the set is non-zero.  This means one must be a
  429.        bit careful about doing things like negation.
  430.     */
  431.     do {
  432.         if (*p) return(0);
  433.     } while (++p < endp);
  434.     
  435.     return(1);
  436. }
  437.  
  438. char *
  439. set_str(a)
  440. set a;
  441. {
  442.     /* Fast convert set a into ASCII char string...
  443.        assumes that all word bits are used in the set
  444.        and that SETSIZE is a multiple of WORDSIZE.
  445.        Trailing 0 bits are removed from the string.
  446.        if no bits are on or set is empty, "" is returned.
  447.     */
  448.     register unsigned *p = a.setword;
  449.     register unsigned *endp = &(a.setword[a.n]);
  450.     static char str_tmp[StrSize+1];
  451.     register char *q = &(str_tmp[0]);
  452.  
  453.     CHK(a);
  454.     if ( a.n==0 ) {*q=0; return( &(str_tmp[0]) );}
  455.     do {
  456.         register unsigned t = *p;
  457.         register unsigned *b = &(bitmask[0]);
  458.         do {
  459.             *(q++) = ((t & *b) ? '1' : '0');
  460.         } while (++b < &(bitmask[WORDSIZE]));
  461.     } while (++p < endp);
  462.  
  463.     /* Trim trailing 0s & NULL terminate the string */
  464.     while ((q > &(str_tmp[0])) && (*(q-1) != '1')) --q;
  465.     *q = 0;
  466.  
  467.     return(&(str_tmp[0]));
  468. }
  469.  
  470. set
  471. set_val(s)
  472. register char *s;
  473. {
  474.     /* Fast convert set ASCII char string into a set.
  475.        If the string ends early, the remaining set bits
  476.        are all made zero.
  477.        The resulting set size is just big enough to hold all elements.
  478.     */
  479.     static set a;
  480.     register unsigned *p, *endp;
  481.  
  482.     set_new(a, strlen(s));
  483.     p = a.setword;
  484.     endp = &(a.setword[a.n]);
  485.     do {
  486.         register unsigned *b = &(bitmask[0]);
  487.         /* Start with a word with no bits on */
  488.         *p = 0;
  489.         do {
  490.             if (*s) {
  491.                 if (*s == '1') {
  492.                     /* Turn-on this bit */
  493.                     *p |= *b;
  494.                 }
  495.                 ++s;
  496.             }
  497.         } while (++b < &(bitmask[WORDSIZE]));
  498.     } while (++p < endp);
  499.  
  500.     return(a);
  501. }
  502.  
  503. /*
  504.  * Or element e into set a.  a can be empty.
  505.  */
  506. void
  507. set_orel(e, a)
  508. unsigned e;
  509. set *a;
  510. {
  511.     CHK((*a));
  512.     if ( e == nil ) return;
  513.     if ( NumWords(e) > a->n ) set_ext(a, NumWords(e));
  514.     a->setword[DIVWORD(e)] |= bitmask[MODWORD(e)];
  515. }
  516.  
  517. /*
  518.  * Or set b into set a.  a can be empty. does nothing if b empty.
  519.  */
  520. void
  521. set_orin(a, b)
  522. set *a, b;
  523. {
  524.     /* Fast set union operation */
  525.     /* size(a) is max(a, b); */
  526.     unsigned int m;
  527.     register unsigned *p,
  528.                       *q    = b.setword,
  529.                       *endq = &(b.setword[b.n]);
  530.  
  531.     CHK((*a)); CHK(b);
  532.     if ( b.n == 0 ) return;
  533.     m = (a->n > b.n) ? a->n : b.n;
  534.     set_ext(a, m);
  535.     p = a->setword;
  536.     do {
  537.         *p++ |= *q++;
  538.     } while ( q < endq );
  539. }
  540.  
  541. void
  542. set_rm(e,a)        /* removes elem arg1 from set arg2 */
  543. unsigned e;
  544. set a;
  545. {
  546.     /* Does not effect size of set */
  547.     CHK(a);
  548.     if ( (e == nil) || (NumWords(e) > a.n) ) return;
  549.     a.setword[DIVWORD(e)] ^= (a.setword[DIVWORD(e)]&bitmask[MODWORD(e)]);
  550. }
  551.  
  552. void
  553. set_clr(a)        /* clears all elems of set arg1 */
  554. set a;
  555. {
  556.     /* Does not effect size of set */
  557.     register unsigned *p = a.setword;
  558.     register unsigned *endp = &(a.setword[a.n]);
  559.     
  560.     CHK(a);
  561.     if ( a.n == 0 ) return;
  562.     do {
  563.         *p++ = 0;
  564.     } while ( p < endp );
  565. }
  566.  
  567. set
  568. set_dup(a)
  569. set a;
  570. {
  571.     set b;
  572.     register unsigned *p,
  573.                       *q    = a.setword,
  574.                       *endq = &(a.setword[a.n]);
  575.     
  576.     CHK(a);
  577.     b = empty;
  578.     if ( a.n == 0 ) return( empty );
  579.     set_ext(&b, a.n);
  580.     p = b.setword;
  581.     do {
  582.         *p++ = *q++;
  583.     } while ( q < endq );
  584.     
  585.     return(b);
  586. }
  587.  
  588. /*
  589.  * Return a nil terminated list of unsigned ints that represents all
  590.  * "on" bits in the bit set.
  591.  *
  592.  * e.g. {011011} --> {1, 2, 4, 5, nil}
  593.  *
  594.  * set_PDQ and set_pdq are useful when an operation is required on each element
  595.  * of a set.  Normally, the sequence is:
  596.  *
  597.  *        while ( set_deg(a) > 0 ) {
  598.  *            e = set_int(a);
  599.  *            set_rm(e, a);
  600.  *            ...process e...
  601.  *        }
  602.  * Now,
  603.  *
  604.  *        t = e = set_pdq(a);
  605.  *        while ( *e != nil ) {
  606.  *            ...process *e...
  607.  *            e++;
  608.  *        }
  609.  *        free( t );
  610.  *
  611.  * We have saved many set calls and have not destroyed set a.
  612.  */
  613. void
  614. set_PDQ(a, q)
  615. set a;
  616. register unsigned *q;
  617. {
  618.     register unsigned *p = a.setword,
  619.                       *endp = &(a.setword[a.n]);
  620.     register unsigned e=0;
  621.  
  622.     CHK(a);
  623.     /* are there any space (possibility of elements)? */
  624.     if ( a.n == 0 ) return;
  625.     do {
  626.         register unsigned t = *p;
  627.         register unsigned *b = &(bitmask[0]);
  628.         do {
  629.             if ( t & *b ) *q++ = e;
  630.             ++e;
  631.         } while (++b < &(bitmask[WORDSIZE]));
  632.     } while (++p < endp);
  633.     *q = nil;
  634. }
  635.  
  636. /*
  637.  * Same as set_PDQ except allocate memory.  set_pdq is the natural function
  638.  * to use.
  639.  */
  640. unsigned *
  641. set_pdq(a)
  642. set a;
  643. {
  644.     unsigned *q;
  645.     int max_deg;
  646.     
  647.     CHK(a);
  648.     max_deg = WORDSIZE*a.n;
  649.     /* assume a.n!=0 & no elements is rare, but still ok */
  650.     if ( a.n == 0 ) return(NULL);
  651.     q = (unsigned *) malloc((max_deg+1)*BytesPerWord);
  652.     if ( q == NULL ) return( NULL );
  653.     set_PDQ(a, q);
  654.     return( q );
  655. }
  656.  
  657. /* a function that produces a hash number for the set
  658.  */
  659. unsigned int set_hash(a,mod)
  660. set a;
  661. register unsigned int mod;
  662. {
  663.     /* Fast hash of set a (assumes all bits used) */
  664.     register unsigned *p = &(a.setword[0]);
  665.     register unsigned *endp = &(a.setword[a.n]);
  666.     register unsigned int i= 0;
  667.  
  668.     CHK(a);
  669.     while (p<endp){
  670.         i = ((i + i + (i<0)) ^ (~ *p));
  671.         p++;
  672.     }
  673.  
  674.     return(((i< 0) ? -i : i) % mod);
  675. }
  676.